| 429.N 叉树的层序遍历 | 您所在的位置：网站首页 › ff14 460搓490 › 429.N 叉树的层序遍历 |
429.N 叉树的层序遍历
|
题目
429.N 叉树的层序遍历 题目大意给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。 样例示例 1：
示例 2：
提示： 树的高度不会超过 1000树的节点总数在 [0,104][0, 10^4][0,104] 之间 思路考虑BFS做法，在每一轮的BFS过程中，需要一次性遍历完同一层的所有节点。比如先让root入队，那么在BFS过程中，会先看当前队列中的元素个数，考虑到BFS在树中遍历，实际上就是层次扩展，那么当前队列中的所有元素都是同一层的，那么就可以把它们依次放进vectorlevel，然后再将level放入答案数组vectorans中，并且对队列中的每一个节点的每一个儿子节点让他们入队，方便下一次的层次扩展。 注意：树的节点总数可以为000，所以当root==nullptr时要返回{}。 时间复杂度：O(n)O(n)O(n)，其中nnn是树中包含的节点个数。（每一个节点恰好遍历一次）空间复杂度：O(n)O(n)O(n)，即为队列需要使用的空间。 代码 // short int long float double bool char string void // array vector stack queue auto const operator // class public private static friend extern // sizeof new delete return cout cin memset malloc // relloc size length memset malloc relloc size length // for while if else switch case continue break system // endl reverse sort swap substr begin end iterator // namespace include define NULL nullptr exit equals // index col row arr err left right ans res vec que sta // state flag ch str max min default charray std // maxn minn INT_MAX INT_MIN push_back insert #include using namespace std; typedef long long ll; typedef pairPII; typedef pairPIS; const int maxn=3e4+50;//注意修改大小 long long read(){long long x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;} ll qpow(ll x,ll q,ll Mod){ll ans=1;while(q){if(q&1)ans=ans*x%Mod;q>>=1;x=(x*x)%Mod;}return ans%Mod;} /* // Definition for a Node. class Node { public:int val;vector children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector _children) {val = _val;children = _children;} }; */class Solution { public:vector levelOrder(Node* root) {if(root==null){return {};}queueq;q.push(root);vectorans;while(!q.empty()){int cnt=q.size();vectorlevel;for(int i=0;iq.push(it);}level.push_back(now->val);}ans.push_back(level);}return ans;} }; |
【本文地址】
公司简介
联系我们
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |